// https://leetcode.cn/problems/rank-transform-of-an-array/
// Created by ade on 2022/7/28.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> arrayRankTransform1(vector<int> &arr) {
        int len = arr.size();
        if(len == 0) return {};
        if(len == 1) return {1};
        vector<int> sortArr = arr;
        sort(sortArr.begin(), sortArr.end());
        unordered_map<int, int> myMap = {};
        myMap[sortArr[0]] = 1;
        int from = 2;
        for (int i = 1; i < sortArr.size(); i++) {
            if (sortArr[i] == sortArr[i - 1]) continue;
            myMap[sortArr[i]] = from;
            from++;
        }
        vector<int> res = {};
        for (auto i : arr) {
            res.emplace_back(myMap[i]);
        }
        return res;
    }

    vector<int> arrayRankTransform(vector<int> &arr) {
        int len = arr.size();
        vector<int> sortArr = arr;
        sort(sortArr.begin(), sortArr.end());
        int k = unique(sortArr.begin(), sortArr.end()) - sortArr.begin();
        for(int i = 0; i < len; i++){
            arr[i] = lower_bound(sortArr.begin(), sortArr.begin() + k, arr[i]) - sortArr.begin() + 1;
        }
        return arr;
    }
};

int main() {
    Solution so;
    vector<int> arr = {40, 10, 20, 30};
    vector<int> a = so.arrayRankTransform(arr);
    for (auto i : a) {
        cout << i << ",";
    }
    cout << endl;
    return 0;

}
